/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/distinct-subsequences
   @Language: C++
   @Datetime: 19-04-11 10:58
   */

// Method 1, Time O(m*n), Space O(m*n)
class Solution {
public:
	/**
	 * @param S: A string
	 * @param T: A string
	 * @return: Count the number of distinct subsequences
	 */
	int numDistinct(string &S, string &T) {
		// write your code here
		if(S.length()<1 || T.length()<1) return T.length()<1?1:0;
		int ls=S.length(), lt=T.length();
		vector<vector<int> > dp(ls+1,vector<int>(lt+1,0));
		dp[0][0]=1;
		for(int i=1; i<=ls; ++i){
			dp[i][0]=dp[i-1][0];
			for(int j=1; j<=i && j<=lt; ++j){
				dp[i][j]=dp[i-1][j]+(S[i-1]==T[j-1]?dp[i-1][j-1]:0);
			}
		}
		return dp[ls][lt];
	}
};


// Method 2, Time O(m*n), Space O(n)
class Solution {
public:
	/**
	 * @param S: A string
	 * @param T: A string
	 * @return: Count the number of distinct subsequences
	 */
	int numDistinct(string &S, string &T) {
		// write your code here
		if(S.length()<1 || T.length()<1) return T.length()<1?1:0;
		int ls=S.length(), lt=T.length();
		vector<vector<int> > dp(2,vector<int>(lt+1,0));
		dp[0][0]=1;
		for(int i=1; i<=ls; ++i){
			dp[i&1][0]=dp[(i-1)&1][0];
			for(int j=1; j<=i && j<=lt; ++j){
				dp[i&1][j]=dp[(i-1)&1][j]+(S[i-1]==T[j-1]?dp[(i-1)&1][j-1]:0);
			}
		}
		return dp[ls&1][lt];
	}
};
